package com.squirrel.michale;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/15 6:51 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1498 {

    public int numSubseq(int[] nums, int target) {

        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int sum = 0;
                if (j == i) {
                    sum = nums[i] * 2;
                    if (sum <= target) {
                        count++;
                    }
                } else {
                    int[] subArray = new int[j - i+1];
                    for (int i1 = 0; i1 < subArray.length; i1++) {
                        subArray[i1] = nums[i+i1];
                    }

                    Arrays.sort(subArray);
                    sum = subArray[0] + subArray[j - i];
                    if (sum <= target) {
                        count++;
                    }
                }

            }
        }

        return count;

    }

//    给定多少个数，能够有多少个sequence
//    当a<=b<=c,且a+c<=target
//    比如{a,b,c}{a}{a,b}{a,c}{a,b,c} 2^(3-1)
//
//    给定n个数，能够有2^(n-1)个
//
//            数组排序后
//    两个指针，一左一右
//    如果nums[left]+nums[right]<=target ,left++
//    如果nums[left]+nums[right]>target ,right--


    public int numSubseq2(int[] nums, int target) {

        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        while (left <= right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else {
                count += 1 << (right - left);
                left++;
            }
        }
        return count;
    }


    public static void main(String[] args) {
//        输入：nums = [3,5,6,7], target = 9
//        输出：4


        LeetCode1498 leetCode1498 = new LeetCode1498();

        int[] nums = new int[]{3, 5, 6, 7};
        int target = 9;
        System.out.println(leetCode1498.numSubseq(nums, target));
        System.out.println(leetCode1498.numSubseq2(nums, target));


    }

}
